package com.adee.java;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * java中Arrays.sort使用了两种排序方法，快速排序和优化的归并排序。
 * 快速排序主要是对哪些基本类型数据(int,short,long等)排序， 而合并排序用于对对象类型进行排序。
 * 使用不同类型的排序算法主要是由于快速排序是不稳定的，而合并排序是稳定的
 * 归并排序相对而言比较次数比快速排序少，移动(对象引用的移动)次数比快速排序多，而对于对象来说，
 * 比较一般比移动耗时。补充一点合并排序的时间复杂度是nlogn, 快速排序的平均时间复杂度也是nlogn，
 * 但是合并排序的需要额外的n个引用的空间。
 *
 */
public class Test060_Arrays_sort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,1,15,6,8,2};
        // 对于数字类型的排序，使用Arrays.sort(int[] a)方法，其采用的算法是：插入排序+双轴快速排序，
        // 元素个数小于47时采用插入排序，超过47时采用双轴快速排序。
        // 双轴快速排序是对普通快速排序的优化版本，使用两个基数，分成三组，排序效率提升，参考：https://blog.csdn.net/mojir/article/details/102949317
        // 插入排序是稳定排序，快速排序是不稳定排序。
        Arrays.sort(arr);

        List<String> list = new ArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("Jack");
        list.add("and");
        list.add("Rose");
        // 对于对象类型的排序，使用Arrays.sort(T[] a, Comparator<? super T> c)方法，其采用的算法是TimSort：二分插入排序+归并排序。
        // 对象排序需要采用稳定排序算法，因为当两个对象判断相等时，需要保证对象原有的先后顺序。
        // 二分插入排序是在普通插入排序的基础上，使用二分查找加速，属于稳定排序。
        // 归并排序也是稳定排序。
        // 为什么使用归并排序？归并排序的比较次数较少，而交换次数较多，对于对象类型的元素，比较时会调用compare方法，比较耗时，而交换
        // 对象地址没什么损耗，因此采用归并排序。
        Collections.sort(list);


    }
}
